package top;

import java.util.*;

/**
 *
 * 课程表二
 *
 * @author chenyw
 * @date 2022/7/18 21:00
 */
public class Top210findOrder {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] input = new int[numCourses];
        Deque<Integer> queue = new LinkedList<>();
        //先找每门课的入度
        for (int[] prerequisite : prerequisites) {
            input[prerequisite[0]]++;
        }
        //找入度为0的节点， 并加入队列
        for (int i = 0; i < numCourses; i++) {
            if (input[i] == 0) {
                queue.addLast(i);
            }
        }

        //拓扑排序的核心代码
        //拓扑排序，一次消除入读为0的节点
        //使用数组存储拓扑排序的过程节点
        int[] res = new int[numCourses + 1];
        int idx = 0;
        while (!queue.isEmpty()) {
            int node = queue.pollFirst();
            res[idx++] = node;
            for (int[] pre : prerequisites) {
                //遍历查找前馈节点为node的节点，让他的入度减一
                if (pre[1] == node) {
                    input[pre[0]]--;
                    if (input[pre[0]] == 0) {
                        queue.addLast(pre[0]);
                    }
                }
            }
        }
        return idx == numCourses ? res :new int[] {};
    }
}
